A 2-hued coloring of a graph $G$ (also known as conditional $(k, 2)$-coloringand dynamic coloring) is a coloring such that for every vertex $v\in V(G)$ ofdegree at least $2$, the neighbors of $v$ receive at least $2$ colors. Thesmallest integer $k$ such that $G$ has a 2-hued coloring with $ k $ colors, iscalled the {\it 2-hued chromatic number} of $G$ and denoted by $\chi_2(G)$. Inthis paper, we will show that if $G$ is a regular graph, then $ \chi_{2}(G)-\chi(G) \leq 2 \log _{2}(\alpha(G)) +\mathcal{O}(1) $ and if $G$ is a graph and$\delta(G)\geq 2$, then $ \chi_{2}(G)- \chi(G) \leq 1+\lceil \sqrt[\delta-1]{4\Delta^{2}} \rceil ( 1+ \log _{\frac{2\Delta(G)}{2\Delta(G)-\delta(G)}}(\alpha(G)) ) $ and in general case if $G$ is a graph, then $ \chi_{2}(G)-\chi(G) \leq 2+ \min \lbrace\alpha^{\prime}(G),\frac{\alpha(G)+\omega(G)}{2}\rbrace $.
展开▼
机译：图$ G $的2色着色（也称为条件$（k，2）$-着色和动态着色）是这样的着色，对于度为V（G）$的每个顶点$ v \ v ，$ v $的邻居会收到至少$ 2 $的颜色。使$ G $具有$ k $颜色的2色着色的最小整数$ k $被称为$ G $的{\ it 2色色数}，用$ \ chi_2（G）$表示。在本文中，我们将证明，如果$ G $是正则图，则$ \ chi_ {2}（G）-\ chi（G）\ leq 2 \ log _ {2}（\ alpha（G））+ \ mathcal {O}（1）$，如果$ G $是图，而$ \ delta（G）\ geq 2 $，则$ \ chi_ {2}（G）-\ chi（G）\ leq 1+ \ lceil \ sqrt [\ delta-1] {4 \ Delta ^ {2}} \ rceil（1+ \ log _ {\ frac {2 \ Delta（G）} {2 \ Delta（G）-\ delta（G）} }（\ alpha（G）））$，一般情况下，如果$ G $是图，则$ \ chi_ {2}（G）-\ chi（G）\ leq 2+ \ min \ lbrace \ alpha ^ { \ prime}（G），\ frac {\ alpha（G）+ \ omega（G）} {2} \ rbrace $。
展开▼
